#include <bits/stdc++.h>
using namespace std;

class Solution {
    public:
        const int INF = 0x3f3f3f3f;
        int coinChange(vector<int>& coins, int amount) {
            int n = coins.size();
            vector<int> dp(amount+1, INF);
            dp[0] = 0;
            for(auto x: coins)
            {
                for(int j = x; j <= amount; j++)
                {
                    dp[j] = min(dp[j], dp[j-x]+1);
                }
            }
            return dp[amount] >= INF ? -1 : dp[amount];
        }
    };